arr = [[0] * n for _ in range(n)]
for _ in range(k): # k: 간선의 개수
    a, b = map(int, input().split())
    arr[a][b] = 1
    arr[b][a] = 0

graph = [[] * for _ in range(n)]
for _ in range(k): # k: 간선의 개수
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

# 파이썬의 기본 재귀 호출 한도는 보통 1,000회로 제한됩니다.  
# 따라서 `sys` 모듈의 `setrecursionlimit=n`으로 최대 한도를 설정합니다.
import sys
sys.setrecursionlimit(n**2)

# 그래프
graph = [[] * for _ in range(n)]
for _ in range(k): # k: 간선의 개수
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    
# 노드 방문 여부
visited = [False] * n

# DFS 로직
def dfs(curr_node):
    visited[curr_node] = True
    
    for next_node in graph[curr_node]:
        if visited[next_node]:
            continue
        dfs(next_node)

import sys

# 이분 그래프 판별 함수
def is_bipartite_graph(curr, color):
    colors[curr] = color
    
    for nxt in graph[curr]:
        if colors[nxt] != 0: # 이미 방문을 한 적이 있는 노드
            if color[nxt] == color[curr]: # 연결된 노드와 현재 노드의 색상이 같으면 이분 그래프가 아니게 된다.
                answer = False
                return False
            continue
        
        # 연결된 노드를 탐색하면서 현재 노드와 다른 색상으로 칠한다. 
        if not is_bipartite_graph(nxt, colors[curr] * -1):
          return False
    
    return True

n, m = map(int, input().split())
sys.setrecursionlimit(n**2)

# 그래프 생성
graph = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
      
colors = [0] * (n + 1) # 색상 기록 배열. 0: 방문하지 않은 노드, 1: 빨간색, -1: 파란색
answer = True
for i in range(1, n + 1):
    if colors[i] == 0: # 아직 방문하지 않았다면
        if not is_bipartite_graph(i, 1):
          answer = False
          break
        
print(answer)

depth  = [0] * n # 각 노드의 방문 깊이(순서)를 기록하는 배열입니다.
has_cycle = False

# cur: 현재 방문한 노드 번호입니다.
# prev: 이전에 방문한 노드 번호입니다.
def dfs(curr, prev):
    for nxt in graph[curr]:
        if prev != nxt: # curr과 연결된 노드인 경우
            if depth[nxt] == 0: # 해당 노드에 처음 방문하는 경우
                depth[nxt] = depth[curr] + 1
                dfs(nxt, curr)
            elif depth[nxt] > depth[curr]: # 연결된 노드가 현재 노드보다 먼저 방문한 경우 -> 사이클 존재
                has_cycle = True
                size = depth[curr] - depth[nxt] + 1 # 사이클의 사이즈를 구한다.    

from collections import deque

def bfs(start):
    visited = [False] * n
    q = deque()
    
    visited[start] = True
    q.append(start)
    
    while q:
        curr = q.popleft()
        
        for next in graph[curr]:
            if visited[next]:
                continue
                
            q.append(next)
            visited[next] = True

from collections import deque

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

def bfs(start_x, start_y):
    visited = [[False] * n for _ in range(n)]
    q = deque((start_x, start_y))
    
    visited[start_x][start_y] = True
    q.append((start_x, start_y))
    
    while q:
        x, y = q.popleft()
        
        for d in range(4):
            next_x, next_y = x + dx[d], y + dy[d]
            
            if not in_array(next_x, next_y):
                continue
            if visited[next_x][next_y]:
                continue
                
            visited[next_x][next_y] = True
            q.append((next_x, next_y))

from collections import deque

graph = ... # 생략

visited = [False] * n
q = deque()

q.append(n)
visited[n] = True

# while문이 실행될 때마다 시작 노드(n)를 기준으로 거리가 1씩 증가하는 노드들만 탐색하게 된다.
# (거리가 1인 노드들 -> 거리가 2인 노드들 -> ...)
while q:
    size = len(q)
    for _ in range(size):
        curr = q.popleft()
        for nxt in graph[curr]:
            if visited[nxt]:
                continue
                
            q.append(nxt)
            visited[nxt] = True